#ifndef _csHashMap_h_
#define _csHashMap_h_

/********************************************************************
	created:	2009/11/06
	created:	6:11:2009   19:46
	filename: 	e:\csEngine\csCoreLib\src\util\csHashMap.h
	file path:	e:\csEngine\csCoreLib\src\util
	file base:	csHashMap
	file ext:	h
	author:		dongchengok
	
	purpose:	hash map
*********************************************************************/
#include "csArray.h"
#include "csString.h"
#define csHASH_INDEX_NONE	-1
#define csHASH_REHASH_FACTOR 1.2

csINLINE u32 GetTypeHash( const u8 i )
{
	return i;
}
csINLINE u32 GetTypeHash( const s8 i )
{
	return i;
}
csINLINE u32 GetTypeHash( const u16 i )
{
	return i;
}
csINLINE u32 GetTypeHash( const s16 i )
{
	return i;
}
csINLINE u32 GetTypeHash( const u32 i )
{
	return i;
}
csINLINE u32 GetTypeHash( const s32 i )
{
	return i;
}
csINLINE u32 GetTypeHash( const u64 i )
{
	return (u32)i+((u32)(i>>32) * 23);
}
csINLINE u32 GetTypeHash( const s64 i )
{
	return (u32)i+((u32)(i>>32) * 23);
}
csINLINE u32 GetTypeHash( void* ptr)
{
	return (u32)ptr;
}
u32 GetTypeHash(const csString& str);

template<typename K,typename V>
class csHashMap
{
public:
	struct Pair
	{
		csINLINE Pair(){}
		csINLINE Pair(const K& k, const V& v):m_key(k),m_value(v){}
		K						m_key;
		V						m_value;
		s32						m_hashNext;
	};
	class iterator
	{
		friend class csHashMap;
	public:
		csINLINE iterator(csArray<Pair>& pairs, s32 index):m_pairs(pairs),m_index(index){}
		Pair&					operator* ();
		Pair*					operator->();
		iterator&				operator++();
		iterator				operator++(s32);
		iterator&				operator--();
		iterator				operator--(s32);
		bool					operator==(const iterator& rhs) const;
		bool					operator!=(const iterator& rhs) const;
								operator bool() const;
		const K&				key() const;
		V&						value();
	protected:
		csArray<Pair>&			m_pairs;
		s32						m_index;
	};
	class const_iterator
	{
		friend class csHashMap;
	public:
		csINLINE const_iterator(const csArray<Pair>& pairs, s32 index):m_pairs(pairs),m_index(index){}
		const Pair&				operator* () const;
		const Pair*				operator->() const;
		const_iterator&			operator++();
		const_iterator			operator++(s32);
		const_iterator&			operator--();
		const_iterator			operator--(s32);
		bool					operator==(const const_iterator& rhs) const;
		bool					operator!=(const const_iterator& rhs) const;
								operator bool() const;
		const K&				key() const;
		const V&				value() const;
	protected:
		const csArray<Pair>&	m_pairs;
		s32						m_index;
	};
	class reverse_iterator
	{
		friend class csHashMap;
	public:
		csINLINE reverse_iterator(csArray<Pair>& pairs, s32 index):m_pairs(pairs),m_index(index){}
		Pair&					operator* ();
		Pair*					operator->();
		reverse_iterator&		operator++();
		reverse_iterator		operator++(s32);
		reverse_iterator&		operator--();
		reverse_iterator		operator--(s32);
		bool					operator==(const reverse_iterator& rhs) const;
		bool					operator!=(const reverse_iterator& rhs) const;
								operator bool() const;
		const K&				key() const;
		V&						value();
	protected:
		csArray<Pair>&			m_pairs;
		s32						m_index;
	};
	class const_reverse_iterator
	{
		friend class csHashMap;
	public:
		csINLINE const_reverse_iterator(const csArray<Pair>& pairs, s32 index):m_pairs(pairs),m_index(index){}
		const Pair&				operator* () const;
		const Pair*				operator->() const;
		const_reverse_iterator&	operator++();
		const_reverse_iterator	operator++(s32);
		const_reverse_iterator&	operator--();
		const_reverse_iterator	operator--(s32);
		bool					operator==(const const_reverse_iterator& rhs) const;
		bool					operator!=(const const_reverse_iterator& rhs) const;
								operator bool() const;
		const K&				key() const;
		const V&				value() const;
	protected:
		const csArray<Pair>&	m_pairs;
		s32						m_index;
	};

public:
	csHashMap();
	csHashMap(s32 capacity);
	csHashMap(const csHashMap<K,V>& hash);
	~csHashMap();

	iterator					begin();
	const_iterator				begin() const;
	iterator					end();
	const_iterator				end() const;
	reverse_iterator			rbegin();
	const_reverse_iterator		rbegin() const;
	reverse_iterator			rend();
	const_reverse_iterator		rend() const;

	void						clear();
	s32							count(const K& k) const;		//fuck the stl function define,1 exist,0 not exist
	bool						hasKey(const K& k) const;		//same to count,my define
	bool						empty() const;
	//does not support equal_range

	//custom function
	//set the k=v, if k does not exist,insert
	void						set(const K& k, const V& v);
	V&							operator[](const K& k);
	const V&					operator[](const K& k) const;
	V*							findValue(const K& k);
	const V*					findValue(const K& k) const;
	//maybe slow
	const K*					findKey(const V& v, const K* fromKey=csNULL) const;
	void						remove(const K& k);

	iterator					erase(iterator where);
	iterator					erase(iterator from, iterator to);

	iterator					find(const K& k);
	const_iterator				find(const K& k) const;

	s32							size() const;
	void						swap(csHashMap<K,V>& rhs);

protected:
	void						_rehash();
	s32							_findIndex(const K& k) const;
	void						_add(const K& k, const V& v);
	void						_relax();

protected:
	s32							m_hashCount;
	s32*						m_hash;
	csArray<Pair>				m_pairs;
};

#include "csHashMap.inl"

#endif // _csHashMap_h_